1. FIELD OF THE INVENTION
This invention relates to the field of digital transmission through analog channels.
2. BACKGROUND ART
Communication of voice and data signals is often accomplished by converting analog signals to digital signals. These digital signals are then transmitted from a transmitting device to a receiving device, converted back to analog, if necessary, and communicated to a user. This digital transmission is often performed through analog channels. Digital information is transmitted in the form of a "symbol" representing a digital value. In some cases, adjacent symbols can overlap, resulting in a phenomenon known as intersymbol interference. This interference can corrupt a digital transmission, leading to errors in the receipt of the digital information.
In a magnetic recording channel, a method for decoding the binary symbol sequence that is outputted from the channel in its corrupted form is required. MLSE decoding has been employed in the past as an effective tool in pulse detectors for receiving and decoding digital transmissions that suffer from intersymbol interference. Because class IV partial response signaling for digital detection is especially suited for the magnetic recording channel, sampled amplitude detection can be applied for magnetic recording. To minimize the propagation of data errors, the signal is turned into a sequence of binary numbers and procedures for determining the maximum likelihood sequence in the presence of noise can be applied. With sequence detection, sequences of bits are detected and processed to minimize error.
Maximum likelihood sequence estimation (MLSE), in particular, the Viterbi algorithm, is used in improving the detection of symbol (pulse) sequences in the presence of noise and intersymbol interference. MLSE is described by G. D. Forney in "The Viterbi Algorithm," Proceedings of the IEEE, Vol. 61, No. 3, March, 1973, pp. 268-278, and by R. W. Wood, etc., in "Viterbi Detection of Class IV Partial Response on a Magnetic Recording Channel," IEEE transactions on communications, Vol. COM-34, No. 5, May, 1986, pp. 454-461.
One of the earliest references (Kobayashi, "Application of Probablistic Decoding to Digital Magnetic Recording Systems," IBM Journal of Research and Development, Vol. 15, No. 1, January 1971, pp. 64-74) to the use of the Viterbi algorithm on the intersymbol interference problem was related to Class IV Partial Response on the Magnetic Recording Channel. In essence, the algorithm provides an iterative method of determining the "best" route along the branches of a trellis. If, for each branch, a "metric" is calculated which corresponds to the logarithm of the probability of that branch, then the Viterbi algorithm can be used to determine the path which accumulates the highest log probability, i.e., the maximum likelihood sequence. In essence, given a received sequence (a.sub.n) where n is an integer time index, choose from among all possible transmitted sequences (b.sub.n) the one which is most likely to cause (an) to be received, i.e., choose (b.sub.n) to maximize P ((a.sub.n).vertline.(b.sub.n)).
With the Viterbi algorithm, data is not decoded as soon as it is received. Instead, a sequence of data, having a predetermined coding depth, following the digit to be decoded is first collected. Then, by computing the path metrics, a limited number of possible messages are selected, each extending throughout the decoding depth far beyond the digit presently to be decoded, with one such survivor sequence ending in each of the data states. The correlation between each survivor sequence and the data actually received is computed for the entire decoding depth under consideration. The highest correlated of the survivor sequences is selected to be the sole survivor sequence. The earliest received digital digits within the decoding depth is then permanently decoded under the temporary assumption that the sole survivor sequence is the correct sequence.
Using partial response signalling allows a better handling of intersymbol interference and allows a more efficient utilization of the bandwidth of a given channel. In partial response systems, a controlled amount of intersymbol interference can be allowed. The partial response system is described by the polynomials 1+D, 1-D and (1-D.sup.2), also called duobinary, dicode, and class-IV, respectively.
The MLSE problem is similar to the problem of finding the shortest route through a certain graph. The Viterbi algorithm arises as a natural recursive solution. This algorithm is often associated with a state diagram which can be illustrated by a trellis as shown in FIG. 1. In the two-state trellis of FIG. 1, each node represents a distinct state at a given time, and each branch represents a transition to some new state at the next instant of time. The trellis is such, that for every possible state sequence, there corresponds a unique path through the trellis, and vice versa. The shortest path segment between two states is called the survivor. For any time interval, there may be more than one survivor, and the shortest complete path must continue through one of these survivors. Thus, at any time K, it is required to remember only the number of survivors and their lengths. To arrive at time K+1, it is required only to extend all time K survivors by one time unit, compute the lengths of the extended path segments, and for each node X.sub.K+1 select the shortest extended path segment terminating in X.sub.K+1 as the corresponding time (K+1) survivor.
For the 2-state trellis shown in FIG. 1, the upper branches and nodes represent the (1) state path and the lower state branches and nodes represent the (-1) or (0) state path. The diagonal branches represent a path that changes state. The node metrics (the accumulated log likelihood) at time K are only a function of the node metrics at K-1 and the path metrics. They are given by: EQU M.sub.K (-1)=max[M.sub.K-1 (-1), M.sub.K-1 (1)-Y.sub.K -V.sub.T ](1) EQU M.sub.K (1)=max[M.sub.K-1 (1), M.sub.K-1 (-1)+Y.sub.K -V.sub.T ](2)
where
M.sub.K (-1)=(-1) metric value at t=K
M.sub.K (1)=(1) metric value at t=K
Y.sub.K =signal amplitude at t=K
V.sub.T =threshold amplitude for Y.sub.K, the most likely value between a sequence pulse and no pulse. V.sub.T typically has a value of approximately Y.sub.K /2.
V.sub.T is set to equal the most likely value between Y.sub.K and noise. V.sub.T could be set by the average peak values of Y.sub.K or by a predetermined or programmable value.
Thus, a change in state for equation (1) will occur if M.sub.k- 1 (1)-Y.sub.K -V.sub.T .gtoreq.M.sub.K- 1(-1), e.g., M.sub.K (-1).noteq.M.sub.K- 1(-1). A change in state for equation (2) will occur if M.sub.K-1 (-1)+Y.sub.K -V.sub.T &gt;M.sub.K-1 (-1), e.g., M.sub.K (1).noteq.M.sub.K-1 (1).
An algorithm is illustrated for a 4-state trellis covering five time units in FIGS. 2A and 2B. FIG. 2A shows the complete trellis, with each branch labeled with a length. In a real application, the lengths are functions of the received data. FIG. 2B shows five recursive steps by which the algorithm determines the shortest path from the initial to the final node. At each stage, only four or fewer survivors are shown, along with their lengths. It can be seen in FIG. 2 that for each time interval, each node outputs two separate path segments and the shortest such path segment is the one that "survives." Thus, by time interval five, the Viterbi algorithm has determined the shortest path.
Two prior art examples of applying the Viterbi algorithm for decoding magnetic recording channel outputs are U.S. Pat. No. 4,644,564 by Dolivo et al. and U.S. Pat. No. 4,087,787 by Acampora. Dolivo et al. disclose a method that uses two survivor sequences and the difference metric between the two metrics is processed. In Dolivo et al., as each sample is received, the prior art patent recursively determines the new pair of survivor sequences and the new difference metric. Dolivo et al. is implemented in a digital format which at times is more accurate but suffers in terms of speed and requires more electronics to implement. Furthermore, resetting of the voltage signals does not occur automatically as is desired.
Acampora employs a Viterbi decoder that comprises a tap delay line and sample-and-hold circuits to perform the path metric operations including storing and updating the path metrics. The path metrics of Acampora can increase without bound with time. To prevent metric overflow, one metric is arbitrarily set to zero. The original value of that metric is first subtracted from all other metrics to preserve the integrity of the difference between the path metrics. A simpler and less arbitrary implementation is desired. Furthermore, these tap delay lines would need to be implemented by variable delays.